Artificial Immune Systems

Dan Taylor
([email-masked])

Abstract:
In recent months the study of Artificial Immune Systems (AIS) has
become more and more popular amongst the academic community. The
first conference on AIS (ICARIS) was held in Canterbury in 2002 and there
have been sessions and publications on AIS at most recent
conferences on artificial intelligence. This article gives an
insight into the power of AIS as a problem solving technique,
focussing on the development of an AIS component set for Delphi.
Two real-world examples are presented: fault prediction in
refrigerators and change detection in Linux configuration files.

Contents

Introduction

The
Human Immune System

Properties
of the Immune System

Architecture
of an Artificial Immune System

The
AIS Component Set

Class
Diagrams

Pattern

Pattern
Set

Matching
Rule

Self
Set Factory

Detector
Set Factory

Change
Monitor

AIS
Test Cases

Refrigeration
Fault Prediction Demo

The
Problem

The
Application

Linux
Hacker Detection Demo

Conclusions

Acknowledgements

Links
and Resources

Introduction

The aims of this article are twofold. Firstly, the article gives
an introduction to Artificial Immune Systems (AIS), their operation
and biological inspiration. Secondly it is hoped that the component
framework developed here will provide a sound foundation for Delphi
developers wishing to exploit AIS technology.

We start by giving a brief overview of the human immune system,
its distributed architecture and the in built mechanisms for
detecting intruders by self/ non self discrimination. The
next section lists the computational aspects of the immune system
which form the basis of data structures and algorithms we might use
to represent it. The architecture of an artificial immune system is
outlined in the next section, followed by details of the components
that were developed for this article. These components are used in
two demo applications which exploit the capabilities of AIS in very
different ways. Finally we conclude with a discussion of how the AIS
approach differs from other AI systems.

Top
of Page

The Human Immune System

The purpose of the human immune system is twofold: It must be
able to detect and categorise foreign bodies (antigens) and
must also be able to destroy or neutralise them to protect us from
their effects. We will concentrate on the first of these, the
ability to detect and categorise antigens. The term antigen refers
to anything which is not part of the body itself, including
bacteria, viruses and suchlike. The job of the immune system is to
differentiate between antigens and the body itself, initiating the
appropriate immune response for foreign bodies, whilst leaving
everything else untouched. This is known as "self/ non-self
discrimination".

The main component of the immune system is the
lymphocyte. Countless millions of these circulate through
the bloodstream and within the tissues of the body. Lymphocytes are
able to recognise non-self (i.e. antigens) by binding to them with
chemical bonds as illustrated in figure 1. The more complimentary
the antigen and lymphocyte the higher the likelihood of a bond
forming. The probability of a bond forming is known as affinity -
high affinity is a high likelihood of a bond forming.

Figure
1: An antigen binding to a lymphocyte with an exact
match

The binding shown in figure 1 is an exact match. However, to
ensure that the immune system can recognise as many antigens as
possible an exact match is not required. A match can occur if a
given number of contiguous features complement each other. The
number of features required to bind before a match can be made is
known as the affinity threshold. Figure 2 shows a lymphocyte and
antigen which match, though not perfectly - there are four
contiguous matching bonds (numbers 2 to 5). Figure 3 shows a
lymphocyte which does not match the antigen as there are no sets of
contiguous features long enough to cause a match (assuming our
affinity threshold is greater than two).

Figure
2: An antigen binding to a lymphocyte with a partial
match

Figure
3: An antigen and lymphocyte which do not match

There are two types of lymphocytes: B cells and T cells. We are
only interested in T cells here. All lymphocytes have three stages
in their lifecycle.

Naive lymphocytes have not yet been "trained" to recognise a
specific antigen

Effector lymphocytes are active within the immune system

Memory lymphocytes exist only to store patterns associated
with antigens that have invaded the body in the past

Lymphocytes are "born" in the lymphoid organs through the
division of existing lymphocyte cells. An unusually large level of
mutation takes place as these lymphocytes divide (known as
Somatic Hypermutation). This means that "child" lymphocytes
are different, though similar to their "parents". This mutation
allows the immune system to learn to categorise new threats. The
process is known as clonal expansion.

During clonal expansion it is possible that new lymphocytes will
be created which incorrectly categorise proteins in the body (self)
as antigens (non-self). These must not be allowed to circulate
around the body as they will cause the immune system to attack the
body's tissues. Therefore, lymphocytes are subjected to a negative
selection process in which they are tested to ensure they do not
categorise self proteins. Lymphocytes which fail the test are
destroyed, those which pass are allowed to circulate around the
body.

When a new antigen invades the body only a few lymphocytes are
able to recognise it. The body must quickly produce more lymphocytes
with high affinity to the antigen, before it has had time to damage
the body too much. For this reason lymphocytes with a high affinity
for antigens are encouraged to reproduce more, that is to say that
recognition stimulates cells to reproduce and mutate. Cells which
mutate to find a better match with the target antigen are encouraged
to divide more. This process creates a large number of lymphocytes
which are specific to the antigen.

The process of going from a reasonably low affinity to an antigen
in a few lymphocytes to produce a large population of high affinity
lymphocytes is called Affinity Maturation. This process
uses reproduction and mutation to create new cells and favours
higher affinity (fitter) cells for reproduction. Essentially,
affinity maturation is a Darwinian evolutionary process.

Once an antigen has been destroyed, the immune system will
remember it, in case it enters the body in future. This memory comes
about through memory lymphocytes, which are created in the same was
as effector lymphocytes but have a longer life span. Memory cells
serve as a reminder of antigen patterns which have posed a threat in
the past. Because memory cells have a high affinity for a given
antigen they are more likely to reproduce. Thus a subset of the
lymphocyte population will continue to have a high affinity for the
remembered antigen.

So, the immune system is diverse in that a large number of
different antigens can be detected, protecting the body from just
about anything which might invade it. The negative selection process
ensures that lymphocytes do not attack the body itself by checking
all new lymphocytes against a set of "self" proteins. It can quickly
respond to a new antigen because lymphocytes with high affinities
are encouraged to reproduce more. The immune system is also able to
remember antigens it has dealt with in the past, by keeping a
population of memory lymphocytes in circulation.

Properties of the Immune System

Some properties of the immune system, computational and
otherwise, are enumerated below.

Recognition: Self/ non-self categorisation
takes place based on intercellular binding

Diversity: A diverse set of lymphocytes is
created, partly by genetic process, to ensure that cells exist
which can bind to any antigen - known or unknown

Learning Clonal expansion, during the first
encounter with an antigen allows the immune system to learn, by
example, to recognise specific antigens

Memory: Memory cells store the patterns
associated with antigens encountered in the past

Distributed Detection: The immune system is
inherently distributed. Lymphocytes and continually recirculated
around the body where they encounter antigenic challenges and
stimulate the appropriate immune response

Self Regulation: Regulation takes place
either locally or on a system wide basis, depending on the
situation

Threshold Mechanism: Immune system response
takes place above a threshold, dictated by the strength of the
chemical binding between lymphocyte and antigen

Dynamic Protection: Affinity maturation
(clonal expansion and somatic hyper-mutation) allows the
generation of high affinity lymphocytes. This dynamically balances
exploration versus exploitation in immunity. Dynamic protection
increases the coverage of the immune system over time

Probabilistic Detection: The cross reaction
in immune response is a stochastic process. Detection is
approximate, so one lymphocyte may bind to several antigens

Architecture of an Artificial Immune System

The building blocks we need to create an artificial immune system
are listed here. This section details the basic structure of the
system, to clarify the link between the biological inspiration and
the implemented system. The next section gives code listings and
other implementation specific details for the Delphi component set.

For any system, be it a computer system, manufacturing process or
real time control application, we can define a pattern of normal
behaviour. For example, a bridge will vibrate only within a given
frequency and amplitude range and we can safely assume that if the
vibration of the bridge leaves this normal range we are heading
towards a potentially dangerous situation. Similarly, the behaviour
of users and processes within a computer system will generally fall
within an acceptable range of values for CPU, memory, network and
resource usage. We are probably safe in assuming that if a process
leaves this range there is something bad happening. Maybe that
process has crashed or a user is attempting to do something
untoward.

Artificial Immune Systems are an ideal tool for detecting these
sorts of incidents. We know from the previous section that the human
immune system is able to differentiate between "self" and "non-self"
and we can use this ability in a computer system to detect when
things go wrong. We define "self" to be the normal operation of the
system. For the bridge example above, "self" is the normal range of
vibrations, loads and suchlike. For the computer security example,
"self" is the normal range of process behaviour. "Non-self" in both
examples is any measurement we make that is outside these ranges.

Figure
4: Normal behaviour of a system

Figure 4 shows an example measurement for a system which is
functioning normally. It could be a vibration measurement of our
bridge as somebody walks across it. (Actually I just used Matlab to
add a couple of sine waves together to give a sensible example).
Figure 5 shows another example measurement for the same system, but
this time there is a noise signal there which represents a fault.
Perhaps the wind is making our bridge unstable? We need out bridge's
immune system to be able to sense this change in behaviour and raise
an alarm so we can investigate the problem.

Figure
5: Abnormal behaviour of a system

The first thing we need to define is a Self Set. The
self set is a set of patterns which represent normal operation of
the system. These patterns will be used by the negative selection
process to ensure that our artificial lymphocytes (T cells) do not
detect "self" (i.e. to ensure that they don't raise an alarm under
normal operation). Our self set will be simply a set of symbol
sequences. Our lymphocytes will also be a set of symbol sequences.
Matching will be measured simply by comparing symbols. The symbols
we'll use here are positive integers. Different problems will need a
different number of symbols, some, such as comparing binary strings,
will need only two (1 and 0), while others will require more. Figure
6 shows how we would convert a continuous sensor reading into a
series of symbols.

Figure
6: Normal behaviour of a system - restricted to 10 symbols
(0 - 9)

Next we create a library of "self" patterns by chopping the above
into a set of shorter sequences. The self set for the above might
look something like listing 1.

Pattern 1: 5 6 6 7 8 8 9
Pattern 2: 9 9 9 9 9 9 9
Pattern 3: 8 8 7 7 6 6 5
Pattern 4: 5 5 4 4 4 4 4

Listing
1: Example self set with 4 patterns and 10 symbols (0 - 9)

Once we have our self set we are ready to start creating the
lymphocytes which will monitor the system. New lymphocytes must be
presented to self patterns to see if they "match" or not. Listing 2
is an example of how the negative selection algorithm will compare
new lymphocytes to self patterns. Remember that any lymphocyte that
matches any self pattern will be destroyed. The length of the
lymphocytes and the self patterns must be the same and it, in this
example, 7.

Exact match - delete lymphocyte

Self pattern: 1 6 7 3 6 2 2
Lymphocyte: 1 6 7 3 6 2 2

Partial match (with threshold of 4) - delete lymphocyte

Self pattern: 1 6 7 3 6 2 2
Lymphocyte: 4 6 7 3 6 3 9

No match (with threshold of 4) - keep lymphocyte

Self pattern: 1 6 7 3 6 2 2
Lymphocyte: 1 6 1 3 6 1 2

Listing
2: Matching self set patterns to lymphocytes

We will use the algorithm in listing 3 to create a set of
lymphocytes known as the Detector Set.

repeat
create a new lymphocyte pattern at random
add lymphocyte to detector set
for each pattern in the self set
if lymphocyte matches self set pattern
delete lymphocyte from detector set
break
end
end
until size limit reached

Listing
3: Negative selection algorithm for creating the detector
set

Once we have generated our detector set we are ready to start
looking for abnormal system behaviour. We do this by discreetising
new data from our system using the rules above, ensuring that we use
the same symbol set, pattern size and suchlike. We can then watch
for errors/ faults by continually applying every artificial
lymphocyte in our detector set to the new data. Because our detector
set is self tolerant (i.e. will never match normal data) we can be
sure that if any detector matches our new data then that data is
indicative of abnormal behaviour. To put it another way: If a
detector matches we have a fault.

To summarise, the following is a list of the components of an
artificial immune system:

Symbols: We must be able to decompose
measurements of our systems into a small set of symbols (the
smaller the better). For the sake of this article, symbols are
positive integers and could be simply [0, 1] for binary, [0 .. 35]
for numbers and letters (a..z, 0..9) or some other appropriate
range.

Pattern: A pattern is a simple structure for
storing a list of symbols. The self set and detector set are
simply lists of patterns.

Self Set: A set of patterns, constructed from
past data, which represents normal operation of our system

Detector Set: A set of lymphocyte patterns,
generated using the negative selection algorithm (above)

The AIS Component Set

Figures 8 shows the class diagram for the artificial immune
system component set. Figure 7 shows the corresponding interfaces.
You will notice that classes to represent the AIS building blocks
detailed in the previous section have been implemented. A couple of
other components have been created to perform other tasks. The
following list is a (very) brief introduction to the AIS component
set. The bulk of this section goes on to give detailed descriptions
of each component, including code listings where appropriate. The
final part of this section details the unit tests which were created
for the AIS components.

Symbol: Symbols are represented as integers.
Therefore there is no "symbol" class.

Pattern: The TAISPattern class stores a list
of symbols using a dynamic array. Self patterns and detectors/
lymphocytes are implemented as TAISPatterns.

PatternSet: The TAISPattern set stores a list
of TAISPattern objects. TAISPatternSet is used to represent the
self set and the detector set.

Self Set Factories Classes which implement
IAISSelfSetFactory are used to load the appropriate self sets from
files.

Detector Set Factory TAISDetectorSetFactory
uses the negative selection algorithm to create a randomly
initialised set of detectors (artificial lymphocytes).

Matching Rule The TAISMatchingRule component
is used to check whether two patterns match, based on a matching
threshold. Both the TAISDetectorSetFactory and the
TAISChangeMonitor make use of the TAISMatchingRule.

Change Monitor The TAISChangeMonitor applies
a detector set to a self set and reports the number and position
of matches which occur.

Class Diagrams

Figures 7 and 8 show class diagrams for the AIS component set.
The figures were exported from Model Maker.

Figure
7: AIS Interfaces

Figure
8: AIS Classes

Pattern

The TAISPattern component stores a list of integers. A dynamic
array (FItems) is exposed through the array property "Items". There
is no functionality for sorting, searching or suchlike, simply
because such functionality is not required.

IAISPattern = interface
function GetItem(I: Integer): Integer;
procedure SetItem(I: Integer; const Value: Integer);
function GetSize: Integer;
procedure SetSize(const Value: Integer);
property Size : Integer read GetSize write SetSize;
property Items [I : Integer] : Integer read GetItem write SetItem;
end;

TAISPattern = class(TComponent, IAISPattern)
private
FItems : array of Integer;
function GetItem(I: Integer): Integer;
procedure SetItem(I: Integer; const Value: Integer);
function GetSize: Integer;
procedure SetSize(const Value: Integer);
public
constructor Create(AOwner : TComponent); override;
destructor Destroy; override;
property Size : Integer read GetSize write SetSize;
property Items [I : Integer] : Integer read GetItem write SetItem;
end;

Listing
4: Code for IAISPattern interface and TAISPattern component

Pattern Set

The TAISPatternSet component stores a list of TAISPattern
components. The TAISPattern set is used to represent the self set
and detector set in our artificial immune system. The "Components"
and "ComponentCount" fields inherited from TComponent are used for
storage. This has the benefit of providing garbage collection at
no extra cost and also removes the need for an additional TList
field for storage. ComponentCount and Components are exposed using
the Count and Patterns properties respectively.

unit UnitAISPatternSet;

interface

uses
UnitAISPattern, Classes;

type

IAISPatternSet = interface
function GetPattern(I: Integer): IAISPattern;
function GetCount: Integer;
function AddPattern : IAISPattern;
property Patterns [I : Integer] : IAISPattern read GetPattern;
property Count : Integer read GetCount;
end;

TAISPatternSet = class(TComponent, IAISPatternSet)
private
function GetPattern(I: Integer): IAISPattern;
function GetCount: Integer;
public
function AddPattern : IAISPattern;
property Patterns [I : Integer] : IAISPattern read GetPattern;
property Count : Integer read GetCount;
end;

implementation

{ TAISPatternSet }

function TAISPatternSet.AddPattern: IAISPattern;
var
New : TAISPattern;
begin
New := TAISPattern.Create(Self);

Result := New;
end;

end.

Listing
5: Code for IAISPatternSet interface and TAISPatternSet
component

Matching Rule

The IAISMatchingRule interface is a template for classes which
implement a matching rule of some sort. The TAISMatchingRule
component implements the interface to provide other components
(namely the TAISDetectorSetFactory and TAISChangeMonitor) with the
ability to compare patterns.

A partial matching rule is implemented, based on a matching
threshold. Two patterns match if there are identical strings with
length greater than or equal to the matching threshold in each. The
function "Matches" takes two patterns and returns true or false as
appropriate. If the function returns true a match has been found.

unit UnitAISMatchingRule;

interface

uses
Classes, UnitAISPattern, Math;

type

IAISMatchingRule = interface
function GetMatchingThreshold: Integer;
procedure SetMatchingThreshold(const Value: Integer);
function Matches(P1, P2 : IAISPattern) : Boolean;
property MatchingThreshold : Integer read GetMatchingThreshold
write SetMatchingThreshold;
end;

TAISMatchingRule = class(TComponent, IAISMatchingRule)
private
FMatchingThreshold: Integer;
function GetMatchingThreshold: Integer;
procedure SetMatchingThreshold(const Value: Integer);
public
function Matches(P1, P2 : IAISPattern) : Boolean;
published
property MatchingThreshold : Integer read GetMatchingThreshold
write SetMatchingThreshold;
end;

procedure Register;

implementation

procedure Register;
begin
RegisterComponents('AIS Components', [TAISMatchingRule]);
end;

{ TAISMatchingRule }

function TAISMatchingRule.Matches(P1, P2: IAISPattern): Boolean;
var
i, Top, BitsMatching : Integer;
Match : Boolean;
begin
Top := min(P1.Size, P2.Size);
Match := False;
BitsMatching := 0;

for i := 0 to Top - 1 do
begin
if P1.Items[i] = P2.Items[i] then
inc(BitsMatching)
else
BitsMatching := 0;

if BitsMatching = FMatchingThreshold then
begin
Match := True;
Break;
end;
end;

Result := Match;
end;

end.

Listing
6: Code for IAISMatchingRule interface and TAISMatchingRule
component

Self Set Factory

The ISelfSetFactory interface is a template for classes which in
some way construct a self set. The most important member of the
interface is the "CreateSelfSet" function, which is responsible for
creating the self set. The only other properties are BinCount and
PartitionSize. PartitionSize controls the size of the patterns in
the pattern set to be constructed. BinCount is the number of integer
symbols which should be used. The name "BinCount" was used to
correspond to the means by which real values are discreetised:
"values between 0 and 1 go in bin 1, values above 10 go in bin 9
etc etc". A more appropriate property name might have been
"SymbolCount".

The component TAISSelfSetFactory and its descendant
TAISSelfSetFromFileFactory are implementations of the
IAISSelfSetFactory interface. They are used to load data for the
fridge fault detection example from ASCII data files exported from
Matlab.

IAISSelfSetFactory = interface
function GetPartitionSize: Integer;
procedure SetPartitionSize(const Value: Integer);
function GetBinCount: Integer;
procedure SetBinCount(const Value: Integer);
function CreateSelfSet(AOwner : TComponent) : IAISPatternSet;
property PartitionSize : Integer read GetPartitionSize
write SetPartitionSize;
property BinCount : Integer read GetBinCount write SetBinCount;
end;

TAISSelfSetFactory = class(TComponent, IAISSelfSetFactory)
private
function GetPartitionSize: Integer;
procedure SetPartitionSize(const Value: Integer);
function GetBinCount: Integer;
procedure SetBinCount(const Value: Integer);
protected
FBinCount : Integer;
FPartitionSize : Integer;
public
function CreateSelfSet(AOwner : TComponent) : IAISPatternSet;
virtual; abstract;
property PartitionSize : Integer read GetPartitionSize
write SetPartitionSize;
property BinCount : Integer read GetBinCount write SetBinCount;
end;

Listing
7: Code for IAISSelfSetFactory interface and
TAISSelfSetFactory component

Detector Set Factory

The TAISDetectorSetFactory component is used to create the
detector set for our artificial immune system. The
GenerateDetectorSet function returns a set of detector patterns
which are generated at random. The negative selection algorithm
presents each new candidate detector to every pattern in the self
set. If a candidate detector matches any self set pattern then it is
discarded and a new one is created. For this reason, the
relationship between the number of patterns to be created
(determined by the DetectorCount property) to the time taken to
create the detector set is exponential. The matching threshold also
has a great effect on the time taken to create the detector set. As
the matching threshold decreases it is harder to generate a
detector, at random, which does not match any pattern in the self
set.

Note that, as mentioned in the comments in listing 8, the random
generation algorithm could be replaced by some heuristic to create
more effective detectors. Also, there is currently no functionality
for preventing the creation of identical detectors. Since identical
detectors will match exactly the same set of patterns, the existence
of identical detectors in the self set is a waste of space. The more
duplicate detectors we have in our detector set the less efficient
our artificial immune system becomes. However, eliminating duplicate
detectors means comparing every candidate detector to the self set
and the detector set. This causes a large increase in the
time taken to generate the detector set.

unit UnitAISDetectorSetFactory;

interface

uses Classes, UnitAISMatchingRule, UnitAISPatternSet, UnitAISPattern;

type

IAISDetectorSetFactory = interface
function GetBinCount: Integer;
function GetMatchingRule: IAISMatchingRule;
function GetPartitionSize: Integer;
function GetSelfSet: IAISPatternSet;
procedure SetBinCount(const Value: Integer);
procedure SetMatchingRule(const Value: IAISMatchingRule);
procedure SetPartitionSize(const Value: Integer);
procedure SetSelfSet(const Value: IAISPatternSet);
function GetDetectorCount: Integer;
procedure SetDetectorCount(const Value: Integer);
function NoMatches(Pattern : IAISPattern) : Boolean;
procedure InitialiseRandomly(Pattern : IAISPattern);
function GenerateDetectorSet(AOwner : TComponent) : IAISPatternSet;
property MatchingRule : IAISMatchingRule read GetMatchingRule
write SetMatchingRule;
property SelfSet : IAISPatternSet read GetSelfSet
write SetSelfSet;
property PartitionSize : Integer read GetPartitionSize
write SetPartitionSize;
property BinCount : Integer read GetBinCount write SetBinCount;
property DetectorCount : Integer read GetDetectorCount
write SetDetectorCount;
end;

TAISDetectorSetFactory = class(TComponent, IAISDetectorSetFactory)
private
function GetBinCount: Integer;
function GetMatchingRule: IAISMatchingRule;
function GetPartitionSize: Integer;
function GetSelfSet: IAISPatternSet;
procedure SetBinCount(const Value: Integer);
procedure SetMatchingRule(const Value: IAISMatchingRule);
procedure SetPartitionSize(const Value: Integer);
procedure SetSelfSet(const Value: IAISPatternSet);
function GetDetectorCount: Integer;
procedure SetDetectorCount(const Value: Integer);
function NoMatches(Pattern : IAISPattern) : Boolean;
procedure InitialiseRandomly(Pattern : IAISPattern);
protected
FMatchingRule : IAISMatchingRule;
FSelfSet : IAISPatternSet;
FBinCount : Integer;
FPartitionSize : Integer;
FDetectorCount : Integer;
public
function GenerateDetectorSet(AOwner : TComponent) : IAISPatternSet;
property MatchingRule : IAISMatchingRule read GetMatchingRule
write SetMatchingRule;
property SelfSet : IAISPatternSet read GetSelfSet write SetSelfSet;
property PartitionSize : Integer read GetPartitionSize
write SetPartitionSize;
property BinCount : Integer read GetBinCount write SetBinCount;
property DetectorCount : Integer read GetDetectorCount
write SetDetectorCount;
end;

implementation

{ TAISDetectorSetFactory }

function TAISDetectorSetFactory.GenerateDetectorSet(AOwner: TComponent):
IAISPatternSet;
var
i : Integer;
DetectorSet : IAISPatternSet;
Current : IAISPattern;
begin
DetectorSet := TAISPatternSet.Create(AOwner);

for i := 0 to FDetectorCount - 1 do
begin
Current := DetectorSet.AddPattern;
Current.Size := FPartitionSize;

repeat
InitialiseRandomly(Current);
until NoMatches(Current);
end;

Result := DetectorSet;
end;

procedure TAISDetectorSetFactory.InitialiseRandomly(Pattern: IAISPattern);
var
i : Integer;
begin
// Totally random rule here for the moment.
// Maybe we could try a better rule which attempts to better mimic
// time series data in future??

for i := 0 to Pattern.Size - 1 do
Pattern.Items[i] := Random(FBinCount);
end;

function TAISDetectorSetFactory.NoMatches(Pattern: IAISPattern): Boolean;
var
i : Integer;
Match : Boolean;
begin
Match := False;

for i := 0 to SelfSet.Count - 1 do
begin
if MatchingRule.Matches(Pattern, SelfSet.Patterns[i]) then
begin
Match := True;
Break;
end;
end;

Result := not Match;
end;

end.

Listing
8: Code for IAISDetectorSetFactory interface and
TAISDetectorSetFactory component

Change Monitor

The TAISChangeMonitor has a very simple function. It checks a
"monitor set" for matches against a detector set. New data from our
system can be inputted into the change monitor, which will compare
it to our pre-trained detector set. The "Check" function returns
true if a match has been found and false if no match was found (i.e.
the monitor set was found to be "self"). If a match was found the
FirstMatch property will be set to the index of the first pattern in
the monitor set which was matched by the detector set. The
MatchCount property gives the number of patterns in the monitor set
which were matched. The CheckFromPattern function can be used to
check the monitor set starting from a given pattern index, thus
CheckFromPattern and FirstMatch can be used to itterate through the
set and find all matching patterns.

unit UnitAISChangeMonitor;

interface

uses Classes, Dialogs, UnitAISPattern, UnitAISPatternSet, UnitAISMatchingRule;

type

IAISChangeMonitor = interface
function GetMatchingRule: IAISMatchingRule;
procedure SetMatchingRule(const Value: IAISMatchingRule);
function GetDetectorSet: IAISPatternSet;
procedure SetDetectorSet(const Value: IAISPatternSet);
function GetMatchCount: Integer;
function GetFirstMatch: Integer;
function Check(MonitorSet : IAISPatternSet) : Boolean;
function CheckFromPattern(MonitorSet : IAISPatternSet; P : Integer) :
Boolean;
property MatchingRule : IAISMatchingRule read GetMatchingRule
write SetMatchingRule;
property DetectorSet : IAISPatternSet read GetDetectorSet
write SetDetectorSet;
property MatchCount : Integer read GetMatchCount;
property FirstMatch : Integer read GetFirstMatch;
end;

TAISChangeMonitor = class(TComponent, IAISChangeMonitor)
private
FMatchingRule : IAISMatchingRule;
FDetectorSet : IAISPatternSet;
FMatchCount : Integer;
FFirstMatch : Integer;
function GetMatchingRule: IAISMatchingRule;
procedure SetMatchingRule(const Value: IAISMatchingRule);
function GetDetectorSet: IAISPatternSet;
procedure SetDetectorSet(const Value: IAISPatternSet);
function Match(Pattern : IAISPattern) : Boolean;
function GetMatchCount: Integer;
function GetFirstMatch: Integer;
public
function Check(MonitorSet : IAISPatternSet) : Boolean;
function CheckFromPattern(MonitorSet : IAISPatternSet; P : Integer) :
Boolean;
published
property MatchingRule : IAISMatchingRule read GetMatchingRule
write SetMatchingRule;
property DetectorSet : IAISPatternSet read GetDetectorSet
write SetDetectorSet;
property MatchCount : Integer read GetMatchCount;
property FirstMatch : Integer read GetFirstMatch;
end;

procedure Register;

implementation

procedure Register;
begin
RegisterComponents('AIS Components', [TAISChangeMonitor]);
end;

{ TAISChangeMonitor }

function TAISChangeMonitor.Check(MonitorSet: IAISPatternSet): Boolean;
begin
Result := CheckFromPattern(MonitorSet, 0)
end;

function TAISChangeMonitor.CheckFromPattern(MonitorSet: IAISPatternSet;
P: Integer): Boolean;
var
i : Integer;
begin
Result := False;
FMatchCount := 0;

for i := P to MonitorSet.Count - 1 do
begin
if Match(MonitorSet.Patterns[i]) then
begin
if FMatchCount = 0 then
FFirstMatch := i;
inc(FMatchCount);
Result := True;
end;
end;
end;

function TAISChangeMonitor.Match(Pattern: IAISPattern): Boolean;
var
i : Integer;
Match : Boolean;
begin
Match := False;

for i := 0 to DetectorSet.Count - 1 do
begin
if MatchingRule.Matches(Pattern, DetectorSet.Patterns[i]) then
begin
Match := True;
Break;
end;
end;

Result := Match;
end;

end.

Listing
9: Code for IAISChangeMonitor interface and
TAISChangeMonitor component

AIS Test Cases

As the components were written they were continually tested using
the DUnit testing framework. Figure 9 shows some tests being run.
Interestingly, as with many artificial intelligence techniques,
artificial immune systems are stochastic. That is to say that they
are random in nature, in fact they draw their strength from
randomness. This makes unit testing a little difficult though. For
example, the test "TestNoIdenticalDetectors" checks that no two
detectors are the same. As you may recall from above, there is no
code in place to stop identical detectors being created, so we're
relying on the fact that it is highly unlikely that two
identical detectors will be created. So the
"TestNoIdenticalDetectors" test will pass most of the time, but fail
some of the time, as shown in figure 10.

Figure
9: DUnit tests - all successful

Hardened unit testers will no doubt be a little worried by this
inaccuracy, but the nature of stochastic systems prevents us from
ever being sure. The issue of provability has dogged AI for many
years, and its not explained here, except to say: How can we
prove that something is random?

Figure
10: DUnitTests with a failure on one of the "stochastic
tests"

Top
of Page

Refrigeration Fault Prediction Demo

The Problem

This demo program shows how we can use our artificial immune
system to detect anomalies in time series data. The data we'll use
is a small snippet of temperature log data recorded from an
experimental refrigeration system. Though it by no means represents
the operation of a normal refrigerator, it does give us some
interesting real-world data to play with. Figure 11 shows the
temperature data with time on the X axis (as per usual) and
temperature on the Y axis. There are 400 data points which represent
samples of the data at regular intervals (every 15 minutes). The
large spikes correspond to automatic defrosts and are part of the
system's normal behaviour.

Figure
11: Fridge temperature data
large version

Figure 12 shows how the fridge data looks before and after
discreetisation. We use 20 symbols here, though we could easily have
used fewer. Note how the discreetised data is greatly simplified but
still manages to represent the general behaviour of the system. This
is exactly what we aim for when choosing the number of symbols we'll
use. Too few symbols would mean loosing the subtleties of system
behaviour, while too many symbols increases the complexity of the
self set and makes detection harder. To make a decision, sadly, as
with so many things in the field of artificial intelligence, we are
forced to combine our intuition with trial and error!

Figure
12: Discreetising the fridge temperature data
large version

Figure 13 shows (in red) the signal we'll be using to test that
the AIS is capable of detecting faults. The fault, for this example,
is totally synthetic. A sine wave is added to the latter half of the
normal temperature data. This simulates a fault in the fridge, but
does not correspond to the patterns you might see in a real fridge
with a real fault.

Figure
13: Normal operation of fridge (blue) and fault condition
(red). Fault starts at time step 200
large version

Figure 14 shows the discreetised plots for the faulty and normal
fridges. Note that, again, a lot of the detail has been lost but it
is still easy to see where the fault starts.

Figure
14: Discreetised plot for normal and faulty temperature
data
large version

The Application

The application developed to demonstrate the use of our
artificial immune system to detect faults in refrigeration data is
pictured in figure 15. The application is very simple, it has a big
image to display the temperature data graphically and a number of
buttons. The rest if this section gives step by step instructions on
how to use it. The source code, executable and data files can be
downloaded by following the links at the bottom of the page.

Figure
15: Fridge demo application when first run

When the application has loaded, click the "Load Self Set"
button. You will be presented with a load dialog in which you should
select the data file containing the normal operation
dataset ("NormalOperation.mat") and click OK. Next, click the
"Display Self Set" button and the normal operation data should be
displayed as shown in figure 16. The grey lines indicate the
boundaries of the patterns in the dataset.

Figure
16: Fridge demo application with loaded self set

Next, create the detector set by clicking the "Create Detector
Set" button. You can look at the detector set by pressing the
"Display Detector Set" button if you like, but it's not very
informative. At any time you can press the "Clear" button to clear
the graph. You can check that the detector set doesn't detect
anything in the self set with which it was trained by clicking
"Check".

Now that the detector set has been created we can load the fault
data. Do this by pressing "Load Self Set" and selecting the
appropriate file "WithFault.mat". Click "Clear" followed by "Display
Self Set" to view it. Make sure you don't click
"Create Detector Set" though. We want to keep the detector set we
trained on the normal data. Figure 17 shows the fault data as
displayed by the program.

Figure
17: Fridge demo application with fault data loaded into
self set

Finally we can check the faulty data we loaded into the self set
by clicking "Check". A number of errors should be reported and the
same number of red lines should be displayed on the graph, as in
figure 18. The red lines correspond to patterns which were matched
by the detector set.

Figure
18: Fridge demo application showing patterns matched by
detector set as red lines

Note that the patterns which were matched are all on the right
hand side of the graph. This is because we only introduced the error
signal in the last half of the data set. The first half of the data
set (the left hand side of the graph) is exactly the same as the
normal operation data, so, because our detector set is guaranteed
(by way of the negative selection algorithm) not to match "self"
patterns, the left hand side of the graph is free of red lines. The
second half of the data, however, contains faults which have,
clearly, been detected by our artificial immune system.

In a real world system we might present data from our test fridge
to the detector set as we measure it, continually monitoring for
matches which imply a fault and raising an alarm as appropriate.

Linux Hacker Detection Demo

The second demo is a very simple one, based on the detection of
alterations to configuration files in Linux. Listing 10 shows part
of a standard Linux configuration file "/etc/passwd". This file
contains a list of the users on the system, one per line, and some
configuration information such as their home directory and user and
group IDs.

root:x:0:0:root:/root:/bin/bash
bin:x:1:1:bin:/bin:/sbin/nologin
daemon:x:2:2:daemon:/sbin:/sbin/nologinologin
...
nscd:x:28:28:NSCD Daemon:/:/bin/false
ident:x:98:98:pident user:/:/sbin/nologin
radvd:x:75:75:radvd user:/:/bin/false
apache:x:48:48:Apache:/var/www:/bin/false
squid:x:23:23::/var/spool/squid:/dev/null
named:x:25:25:Named:/var/named:/bin/false
pcap:x:77:77::/var/arpwatch:/sbin/nologin
mysql:x:27:27:MySQL Server:/var/lib/mysql:/bin/bash
dan:x:500:500:Dan Taylor:/home/dan:/bin/bash
ian:x:502:501:Ian Wallace:/home/ian:/bin/bash
...

Listing
10: Part of a pretty normal /etc/passwd file from a typical
Linux system

It is quite possible that a Linux hacker, once they have gained
access to a system, might attempt to add a new user to /etc/fstab.
To test that our artificial immune system can detect configuration
file changes we'll create a copy of the file which we'll edit in the
style of a hacker. The red line in listing 11 shows the input added
by our "evil" hacker.

...
dan:x:500:500:Dan Taylor:/home/dan:/bin/bash
ian:x:502:501:Ian Wallace:/home/ian:/bin/bash
evil:x:999:501:Evil dummy user:/home/dan:/bin/bash
tom:x:503:503:Tom "Lone Axeman" Owen:/home/tom:/bin/bash
ron:x:504:504:The Great Rontana:/home/ron:/bin/bash
...

Listing
11: Part of an edited copy of /etc/passwd where a hacker
has added a new user ("evil")

Figure 18 shows the user interface of our Linux hacker detection
example program. The buttons at the bottom so exactly what the
buttons in our previous example did. The white area, in this
program, is a list box which is used to display the character based
patterns.

Figure
19: The hacker detection program

Figure 20 shows the Linux hacker detection program with the self
set loaded. To encode the text file as a list of integers, in this
example, the program simply uses the ordinal (ASCII) value of each
character. This isn't a very good method to use because it leaves us
with a very large symbol set (128 values at least), most of which we
won't ever encounter. A much better technique would be to use a
smaller number of symbols corresponding to the characters 'a' to 'z'
and 'A' to 'Z', the digits '0' to '9' and some useful punctuation
such as '/', '.', '&' etc. We could easily encode all other
characters we encounter as a single integer value, corresponding to
"other".

Figure
20: The hacker detection program showing the self set
(passwd.txt)

Because of the large number of symbols we are using we are forced
to use a much bigger detector set and a much lower matching
threshold in order to be able to detect changes. For this reason the
detector set takes a lot longer to create. Figure 21 shows the
detector set. Note that there are a large number of "garbage"
characters in the detector set which could have been avoided if we'd
used a more sensible encoding.

Figure
21: The hacker detection program displaying the detector
set created

We then load the edited file into the self set. Figure 22 shows
the patterns which correspond to the evil user's entry in the file.

Figure
22: The hacker detection program showing the self set
loaded from the edited file - note additions on lines 141 and 146

Figure 23 shows the result of checking the edited self set. Note
that the AIS has managed to detect patterns corresponding to the
correct lines in the file.

Figure
23: The hacker detection program showing the lines on which
matches were found

The Linux hacker detection program is a successful, though
extraordinarily simple demonstration of the ability of artificial
immune systems to detect changes in computer systems. I could be
argued the it would be much easier to simply compare the
configuration file to a backup copy and raise an alarm if it has
changed. If we were monitoring only /etc/passwd then this would be
an entirely valid solution. However, there are hundreds of
configuration files even on the most basic Linux system (and, in
Windows, the registry contains many thousands of keys). If we were
to watch for changes in these files by comparing them to backup
copies then we would waste a lot of space storing duplicate files.
However, given what we know about artificial immune systems, it is
easy to see that the detector set we would need to monitor
all configuration files would be much more compact. This is
because detectors are able to find not just one, but many possible
alterations in the system they monitor.

Conclusions

In this article a simple implementation of an artificial immune
system has been presented. Two example problem areas have also been
explored with promising results. Hopefully the article will provide
a good starting point for Delphi developers who wish to use
artificial immune systems in their applications.

Artificial immune systems are a relatively new area of artificial
intelligence research which is extremely promising. A vast array of
unexplored application areas exists, including many problem areas
for which traditional AI techniques (neural networks, genetic
algorithms, expert systems) were not appropriate. The main strength
of the AIS is the fact that it is able to learn without any negative
training examples. This lifts the burden placed on AI developers to
include examples of every possible fault or anomaly which can
occur in their system. Being able to train an anomaly detection
system using only experience of what is "normal" is a huge
advantage.

Some other advantages of artificial immune systems are:

Simple training algorithm: learning involves
only the random generation of detectors and the application of the
negative selection algorithm

"Self taught": no user intervention
is required when creating the detector set

Simple matching rule: Once a detector set has
been generated the detection of anomalies is very simple. This
means that detection is also computationally inexpensive

Inherently distributed: Artificial immune
systems are distributed by nature. The generation of the detector
set and subsequent monitoring/ classification can be performed on
different nodes of a distributed system with no modification to
the architecture or computational overhead

Despite their many advantages, artificial immune systems are by
no means perfect. As with all artificial intelligence techniques
they have a number of drawbacks which can not be ignored:

Provability: Artificial immune systems draw
their strength from randomness. The generation of the detector set
is random and, therefore, it is impossible to prove that an AIS
will be able to find every possible novelty or fault
which may occur.

Parameter setup: A common problem with AI
systems is that the setup of system parameters, such as the size
of self and detector sets and the matching threshold, is based on
guesswork by the developer.

No unified model: The architecture presented
here is the most popular but my no means the only type of AIS.
Many others exist, details of which can be found in literature.
Until agreement is reached on exactly how an artificial immune
system should work, there will always be the opportunity for
misunderstanding amongst developers.

Though this article covers the basics of artificial immune
systems, it barely scrapes the surface of this extremely complex
field. We conclude with a small list of questions which are not
answered here, in the hope that they will inspire more research:

How can we continually adapt our detector set to cope with
changes in the system over time?

Are there better techniques for generating detectors?

Would a binary (or similar) encoding cut down the size of the
detector set?

Can we adjust our detector set to become more sensitive to
particular anomalies?

Do we need to compare new patterns to every detector?

What's the best method for distributing our AIS?

Acknowledgements

I would like to thank my employers JTL Systems Ltd for
their continued support and for providing some of the data used in
this article. Also, the UK Borland User Group at a meeting of which this
article was first presented (February 2003).

Links and Resources

Downloads

Note that you download and use software and source code entirely
at your own risk. No responsibility will be taken, by anyone, for
any damage of any kind which may or may not be caused by the use of
these files.

That said, please do feel free to download and use the software,
I ask only that I am credited as the original author and that you e-mail me a brief outline
of your project - simply for the sake of curiosity. Also, if you
make amendments, alterations or upgrades to the code which you feel
are beneficial, please send me a copy so I can update what is
included in this article.

File

Description

fridge.zip

Fridge data sets

fridgedemo.zip

All code for the fridge demo, including code for the AIS
component set

FridgeDemo.exe

The fridge demo program, ready to run - though you'll need
the data files too!

linux.zip

Linux data sets

linuxdemo.zip

All code for the Linux demo, including code for the AIS
component set (again!)

LinuxDemo.exe

The Linux demo program (will work with any text file...)

Links

Logical Genetics Resources:

Logical Genetics Paper Database A list of many
academic papers and publications relating to AIS can be found
here, along with any of my associated research notes

Logical Genetics Forums For your comments and
questions.

Artificial Immune Systems:

"Artificial Immune Systems and their Applications"
This book, edited by Dipankar Dasgupta, is a must-have for
all those who are interested in AIS

2nd International Conference on
Artificial Immune Systems To be held in Edinburgh in
September 2003.

An Overview of the Immune System A great
introduction to the immune system for computer scientists. From
the University of New Mexico.

Delphi Stuff:

Model Maker The CASE tool I used to create the
class hierarchy and diagrams in this article

DUnit
A fantastic unit testing framework which allowed me to write
the code for this article in a very short time

"Artificial
Immune Systems" (all text and figures) © 2003 Dan Taylor, Logical
Genetics